package 动态规划;

import java.util.Arrays;

public class No70爬楼梯 {

    /**
     * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
     * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
     * 注意：给定 n 是一个正整数。
     *
     * 示例 1：
     * 输入： 2
     * 输出： 2
     * 解释： 有两种方法可以爬到楼顶。
     * 1.  1 阶 + 1 阶
     * 2.  2 阶
     * 示例 2：
     * 输入： 3
     * 输出： 3
     * 解释： 有三种方法可以爬到楼顶。
     * 1.  1 阶 + 1 阶 + 1 阶
     * 2.  1 阶 + 2 阶
     * 3.  2 阶 + 1 阶
     */

    /**
     * 变种题目,可以走的步数由调用者传入,不一定只能走一步或者两步
     * @param n 楼梯书
     * @param step 可走步数
     * @return 多少种走法
     * 用动态规划求解,找出一层楼有多少种次数;假设步数为1,2
     * f(0)=0;
     * f(1)=f(0)+1;
     * f(2)=(f(1)+1)+(f(0)+2)
     * f(3)=(f(2)+1)+(f(1)+2)
     */
    public int climbStairs(int n,int[] step) {

        int[] dp=new int[n+1];
        dp[0]=0;
        Arrays.sort(step);//步数排序

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < step.length; j++) {
                if(i<step[j]){
                    //从0开始一步也跨不上来
                    break;//因为排过序的步数,所以可以break
                }
                /**
                 * 反正记住,当前n层方法等于(之前n-j层之和,不用+1)
                 * 一般为了不用三元运算符,就直接将dp[0]设置为1即可
                 */
                dp[i]+=dp[i-step[j]]==0?1:dp[i-step[j]];
            }
        }

        return dp[n];
    }

    public static void main(String[] args) {
        No70爬楼梯 n=new No70爬楼梯();
        int result = n.climbStairs(25, new int[]{1, 2});
        System.out.println(result);
    }

}
